{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{3}"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "r = set([1,2,3]) & set([3,4,5])\n",
    "r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import combinations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(0, 1), (0, 2), (1, 2)]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(combinations(range(3), 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{1, 2, 3, 4, 5}"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "r = set([1,2,3]) | set([3,4,5])\n",
    "r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 1 1\n"
     ]
    }
   ],
   "source": [
    "for a,b,c in zip([1,2,3], [1], [1,2]):\n",
    "    print(a,b,c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [],
   "source": [
    "inputs = [\n",
    "    [1,2,3],\n",
    "    [1,2],\n",
    "    [2],\n",
    "    [3],\n",
    "    [4, 5],\n",
    "    [6],\n",
    "    [5, 6]\n",
    "]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[{'Alex', 'Alex0@m.co', 'Alex4@m.co', 'Alex5@m.co'},\n",
       " {'Ethan', 'Ethan0@m.co', 'Ethan3@m.co'},\n",
       " {'Kevin', 'Kevin2@m.co', 'Kevin4@m.co'},\n",
       " {'Gabe', 'Gabe0@m.co', 'Gabe2@m.co', 'Gabe3@m.co'},\n",
       " {'Gabe', 'Gabe2@m.co', 'Gabe3@m.co', 'Gabe4@m.co'}]"
      ]
     },
     "execution_count": 104,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "inputs = [set(input) for input in inputs]\n",
    "inputs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[{'Alex4@m.co', 'Alex', 'Alex5@m.co', 'Alex0@m.co'}, {'Ethan3@m.co', 'Ethan0@m.co', 'Ethan'}, {'Kevin2@m.co', 'Kevin4@m.co', 'Kevin'}, {'Gabe3@m.co', 'Gabe2@m.co', 'Gabe', 'Gabe0@m.co', 'Gabe4@m.co'}, {'Gabe2@m.co', 'Gabe3@m.co', 'Gabe', 'Gabe4@m.co'}]\n"
     ]
    }
   ],
   "source": [
    "outputs = [inputs[0]]\n",
    "E0 = inputs[1:]\n",
    "E1 = []\n",
    "while True:\n",
    "    if len(E0) == 1:\n",
    "        e = E0[0]\n",
    "        fine = False\n",
    "        for index, target in enumerate(outputs):\n",
    "            if len(target & e) > 0:\n",
    "                outputs[index] = target | e\n",
    "                fine == True\n",
    "        if fine == False:\n",
    "            if e not in outputs:\n",
    "                outputs.append(e)\n",
    "        break\n",
    "            \n",
    "    #print(E0)\n",
    "    #print(outputs)\n",
    "    for index, target in enumerate(outputs):\n",
    "        for e in E0:\n",
    "            if len(target & e) > 0:\n",
    "                outputs[index] = target | e\n",
    "            else:\n",
    "                if e not in E1:\n",
    "                    E1.append(e)\n",
    "        E0 = E1\n",
    "        if len(E0) == 0:\n",
    "            break\n",
    "    if len(E0) == 0:\n",
    "        break\n",
    "    else:\n",
    "        if E0[0] not in outputs:\n",
    "            outputs.append(E0[0])\n",
    "            E0 = E0[1:]\n",
    "            E1 = E1[1:]\n",
    "print(outputs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = set([1,2,3])\n",
    "b = set([2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "metadata": {},
   "outputs": [],
   "source": [
    "def makeGroups(inputs):\n",
    "    inputs = [set(input) for input in inputs]\n",
    "    outputs = [inputs[0]]\n",
    "    E0 = inputs[1:]\n",
    "    E1 = []\n",
    "    while True:\n",
    "        if len(E0) == 1:\n",
    "            e = E0[0]\n",
    "            fine = False\n",
    "            for index, target in enumerate(outputs):\n",
    "                if len(target & e) > 0:\n",
    "                    outputs[index] = target | e\n",
    "                    fine = True\n",
    "            if fine == False:\n",
    "                if e not in outputs:\n",
    "                    outputs.append(e)\n",
    "            break\n",
    "\n",
    "        #print(E0)\n",
    "        #print(outputs)\n",
    "        for index, target in enumerate(outputs):\n",
    "            for e in E0:\n",
    "                if len(target & e) > 0:\n",
    "                    outputs[index] = target | e\n",
    "                else:\n",
    "                    if e not in E1:\n",
    "                        E1.append(e)\n",
    "            E0 = E1\n",
    "            if len(E0) == 0:\n",
    "                break\n",
    "        if len(E0) == 0:\n",
    "            break\n",
    "        else:\n",
    "            if E0[0] not in outputs:\n",
    "                outputs.append(E0[0])\n",
    "                E0 = E0[1:]\n",
    "                E1 = E1[1:]\n",
    "    return outputs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[['Alex', 'Alex5@m.co', 'Alex4@m.co', 'Alex0@m.co'],\n",
      " ['Ethan', 'Ethan3@m.co', 'Ethan3@m.co', 'Ethan0@m.co'],\n",
      " ['Kevin', 'Kevin4@m.co', 'Kevin2@m.co', 'Kevin2@m.co'],\n",
      " ['Gabe', 'Gabe0@m.co', 'Gabe3@m.co', 'Gabe2@m.co'],\n",
      " ['Gabe', 'Gabe3@m.co', 'Gabe4@m.co', 'Gabe2@m.co']]\n",
      "\n",
      "[['Alex', 'Alex0@m.co', 'Alex4@m.co', 'Alex5@m.co'],\n",
      " ['Ethan', 'Ethan0@m.co', 'Ethan3@m.co'],\n",
      " ['Kevin', 'Kevin2@m.co', 'Kevin4@m.co'],\n",
      " ['Gabe', 'Gabe0@m.co', 'Gabe2@m.co', 'Gabe3@m.co', 'Gabe4@m.co']]\n",
      "\n",
      "[['Alex', 'Alex0@m.co', 'Alex4@m.co', 'Alex5@m.co'],\n",
      " ['Ethan', 'Ethan0@m.co', 'Ethan3@m.co'],\n",
      " ['Gabe', 'Gabe0@m.co', 'Gabe2@m.co', 'Gabe3@m.co', 'Gabe4@m.co'],\n",
      " ['Kevin', 'Kevin2@m.co', 'Kevin4@m.co']]\n"
     ]
    }
   ],
   "source": [
    "from typing import List\n",
    "from pprint import pprint\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        raw_data = dict()\n",
    "        for account in accounts:\n",
    "            name = account[0]\n",
    "            if name in raw_data.keys():\n",
    "                raw_data[name].append(account[1:])\n",
    "            else:\n",
    "                raw_data[name] = [account[1:]]\n",
    "        results = []\n",
    "        for name, emails in raw_data.items():\n",
    "            groups = makeGroups(emails)\n",
    "            for group in groups:\n",
    "                group = list(group)\n",
    "                group.sort()\n",
    "                results.append([name] + group)\n",
    "        return results\n",
    "\n",
    "#inputs = [[\"John\",\"johnsmith@mail.com\",\"john_newyork@mail.com\"],[\"John\",\"johnsmith@mail.com\",\"john00@mail.com\"],[\"Mary\",\"mary@mail.com\"],[\"John\",\"johnnybravo@mail.com\"]]\n",
    "inputs = [[\"Alex\",\"Alex5@m.co\",\"Alex4@m.co\",\"Alex0@m.co\"],[\"Ethan\",\"Ethan3@m.co\",\"Ethan3@m.co\",\"Ethan0@m.co\"],[\"Kevin\",\"Kevin4@m.co\",\"Kevin2@m.co\",\"Kevin2@m.co\"],[\"Gabe\",\"Gabe0@m.co\",\"Gabe3@m.co\",\"Gabe2@m.co\"],[\"Gabe\",\"Gabe3@m.co\",\"Gabe4@m.co\",\"Gabe2@m.co\"]]\n",
    "outputs = [[\"Alex\",\"Alex0@m.co\",\"Alex4@m.co\",\"Alex5@m.co\"],[\"Ethan\",\"Ethan0@m.co\",\"Ethan3@m.co\"],[\"Gabe\",\"Gabe0@m.co\",\"Gabe2@m.co\",\"Gabe3@m.co\",\"Gabe4@m.co\"],[\"Kevin\",\"Kevin2@m.co\",\"Kevin4@m.co\"]]\n",
    "pprint(inputs)\n",
    "print()\n",
    "pprint(Solution().accountsMerge(inputs))\n",
    "print()\n",
    "pprint(outputs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 145,
   "metadata": {},
   "outputs": [],
   "source": [
    "def makeGroups(inputs):\n",
    "    inputs = [p[1:] for p in inputs]\n",
    "    inputs = [set(input) for input in inputs]\n",
    "    outputs = [inputs[0]]\n",
    "    E0 = inputs[1:]\n",
    "    E1 = []\n",
    "    while True:\n",
    "        if len(E0) == 1:\n",
    "            e = E0[0]\n",
    "            fine = False\n",
    "            for index, target in enumerate(outputs):\n",
    "                if len(target & e) > 0:\n",
    "                    outputs[index] = target | e\n",
    "                    fine = True\n",
    "            if fine == False:\n",
    "                if e not in outputs:\n",
    "                    outputs.append(e)\n",
    "            break\n",
    "        print(\"EEEEEEEE0\", E0)\n",
    "        print(\"out0\", outputs)\n",
    "        for index, target in enumerate(outputs):\n",
    "            for e in E0:\n",
    "                if len(target & e) > 0:\n",
    "                    outputs[index] = outputs[index] | e\n",
    "                    print(target | e)\n",
    "                else:\n",
    "                    if e not in E1:\n",
    "                        E1.append(e)\n",
    "            E0 = E1\n",
    "            if len(E0) == 0:\n",
    "                break\n",
    "        print(\"EEEEEEEE1\", E0)\n",
    "        print(\"out1\", outputs)\n",
    "        if len(E0) == 0:\n",
    "            break\n",
    "        else:\n",
    "            if E0[0] not in outputs:\n",
    "                outputs.append(E0[0])\n",
    "                E0 = E0[1:]\n",
    "                E1 = E1[1:]\n",
    "    return outputs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 146,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[['David', 'David0@m.co', 'David1@m.co'],\n",
      " ['David', 'David3@m.co', 'David4@m.co'],\n",
      " ['David', 'David4@m.co', 'David5@m.co'],\n",
      " ['David', 'David2@m.co', 'David3@m.co'],\n",
      " ['David', 'David1@m.co', 'David2@m.co']]\n",
      "\n",
      "EEEEEEEE0 [{'David4@m.co', 'David3@m.co'}, {'David4@m.co', 'David5@m.co'}, {'David2@m.co', 'David3@m.co'}, {'David2@m.co', 'David1@m.co'}]\n",
      "out0 [{'David0@m.co', 'David1@m.co'}]\n",
      "{'David2@m.co', 'David0@m.co', 'David1@m.co'}\n",
      "EEEEEEEE1 [{'David4@m.co', 'David3@m.co'}, {'David4@m.co', 'David5@m.co'}, {'David2@m.co', 'David3@m.co'}]\n",
      "out1 [{'David2@m.co', 'David0@m.co', 'David1@m.co'}]\n",
      "EEEEEEEE0 [{'David4@m.co', 'David5@m.co'}, {'David2@m.co', 'David3@m.co'}]\n",
      "out0 [{'David2@m.co', 'David0@m.co', 'David1@m.co'}, {'David4@m.co', 'David3@m.co'}]\n",
      "{'David2@m.co', 'David1@m.co', 'David0@m.co', 'David3@m.co'}\n",
      "{'David4@m.co', 'David5@m.co', 'David3@m.co'}\n",
      "{'David2@m.co', 'David4@m.co', 'David3@m.co'}\n",
      "EEEEEEEE1 [{'David4@m.co', 'David5@m.co'}, {'David2@m.co', 'David3@m.co'}]\n",
      "out1 [{'David2@m.co', 'David1@m.co', 'David0@m.co', 'David3@m.co'}, {'David2@m.co', 'David4@m.co', 'David5@m.co', 'David3@m.co'}]\n",
      "\n",
      "[{'David2@m.co', 'David1@m.co', 'David0@m.co', 'David3@m.co'},\n",
      " {'David2@m.co', 'David4@m.co', 'David5@m.co', 'David3@m.co'},\n",
      " {'David4@m.co', 'David5@m.co'}]\n",
      "\n",
      "[['David0@m.co',\n",
      "  'David1@m.co',\n",
      "  'David2@m.co',\n",
      "  'David3@m.co',\n",
      "  'David4@m.co',\n",
      "  'David5@m.co']]\n"
     ]
    }
   ],
   "source": [
    "inputs = [[\"David\",\"David0@m.co\",\"David1@m.co\"],[\"David\",\"David3@m.co\",\"David4@m.co\"],[\"David\",\"David4@m.co\",\"David5@m.co\"],[\"David\",\"David2@m.co\",\"David3@m.co\"],[\"David\",\"David1@m.co\",\"David2@m.co\"]]\n",
    "expected = [[\"David0@m.co\",\"David1@m.co\",\"David2@m.co\",\"David3@m.co\",\"David4@m.co\",\"David5@m.co\"]]\n",
    "pprint(inputs)\n",
    "\n",
    "print()\n",
    "\n",
    "outputs = makeGroups(inputs)\n",
    "print()\n",
    "pprint(outputs)\n",
    "print()\n",
    "pprint(expected)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 147,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 148,
   "metadata": {},
   "outputs": [],
   "source": [
    "def valid(inputs):\n",
    "    c = Counter()\n",
    "    for l in inputs:\n",
    "        c.update(l)\n",
    "    print(c)\n",
    "    return all([v == 1 for v in c.values()])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 149,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[['David0@m.co', 'David1@m.co', 'David2@m.co', 'David3@m.co', 'David4@m.co', 'David5@m.co']]\n",
      "Counter({'David0@m.co': 1, 'David1@m.co': 1, 'David2@m.co': 1, 'David3@m.co': 1, 'David4@m.co': 1, 'David5@m.co': 1})\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 149,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print(expected)\n",
    "valid(expected)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 152,
   "metadata": {},
   "outputs": [],
   "source": [
    "def makeGroups(inputs):\n",
    "    inputs = [set(input) for input in inputs]\n",
    "    outputs = [inputs[0]]\n",
    "    E0 = inputs[1:]\n",
    "    E1 = []\n",
    "    while True:\n",
    "        if len(E0) == 1:\n",
    "            e = E0[0]\n",
    "            fine = False\n",
    "            for index, target in enumerate(outputs):\n",
    "                if len(target & e) > 0:\n",
    "                    outputs[index] = target | e\n",
    "                    fine = True\n",
    "            if fine == False:\n",
    "                if e not in outputs:\n",
    "                    outputs.append(e)\n",
    "            break\n",
    "        print(\"EEEEEEEE0\", E0)\n",
    "        print(\"out0\", outputs)\n",
    "        for index, target in enumerate(outputs):\n",
    "            for e in E0:\n",
    "                if len(target & e) > 0:\n",
    "                    outputs[index] = outputs[index] | e\n",
    "                    print(target | e)\n",
    "                else:\n",
    "                    if e not in E1:\n",
    "                        E1.append(e)\n",
    "            E0 = E1\n",
    "            if len(E0) == 0:\n",
    "                break\n",
    "        print(\"EEEEEEEE1\", E0)\n",
    "        print(\"out1\", outputs)\n",
    "        if len(E0) == 0:\n",
    "            break\n",
    "        else:\n",
    "            if E0[0] not in outputs:\n",
    "                outputs.append(E0[0])\n",
    "                E0 = E0[1:]\n",
    "                E1 = E1[1:]\n",
    "    return outputs\n",
    "\n",
    "def makeGroups2(inputs):\n",
    "    while True:\n",
    "        outputs = makeGroups(inputs)\n",
    "        if valid(outputs):\n",
    "            return outputs\n",
    "        else:\n",
    "            inputs = outputs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 155,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[['David', 'David0@m.co', 'David1@m.co'],\n",
      " ['David', 'David3@m.co', 'David4@m.co'],\n",
      " ['David', 'David4@m.co', 'David5@m.co'],\n",
      " ['David', 'David2@m.co', 'David3@m.co'],\n",
      " ['David', 'David1@m.co', 'David2@m.co']]\n",
      "\n",
      "EEEEEEEE0 [{'David4@m.co', 'David', 'David3@m.co'}, {'David4@m.co', 'David', 'David5@m.co'}, {'David2@m.co', 'David', 'David3@m.co'}, {'David2@m.co', 'David', 'David1@m.co'}]\n",
      "out0 [{'David0@m.co', 'David', 'David1@m.co'}]\n",
      "{'David4@m.co', 'David', 'David1@m.co', 'David0@m.co', 'David3@m.co'}\n",
      "{'David4@m.co', 'David', 'David1@m.co', 'David0@m.co', 'David5@m.co'}\n",
      "{'David2@m.co', 'David', 'David1@m.co', 'David0@m.co', 'David3@m.co'}\n",
      "{'David2@m.co', 'David', 'David1@m.co', 'David0@m.co'}\n",
      "EEEEEEEE1 []\n",
      "out1 [{'David4@m.co', 'David1@m.co', 'David2@m.co', 'David', 'David0@m.co', 'David5@m.co', 'David3@m.co'}]\n",
      "Counter({'David4@m.co': 1, 'David1@m.co': 1, 'David2@m.co': 1, 'David': 1, 'David0@m.co': 1, 'David5@m.co': 1, 'David3@m.co': 1})\n",
      "\n",
      "[{'David',\n",
      "  'David0@m.co',\n",
      "  'David1@m.co',\n",
      "  'David2@m.co',\n",
      "  'David3@m.co',\n",
      "  'David4@m.co',\n",
      "  'David5@m.co'}]\n",
      "\n",
      "[['David0@m.co',\n",
      "  'David1@m.co',\n",
      "  'David2@m.co',\n",
      "  'David3@m.co',\n",
      "  'David4@m.co',\n",
      "  'David5@m.co']]\n"
     ]
    }
   ],
   "source": [
    "inputs = [[\"David\",\"David0@m.co\",\"David1@m.co\"],[\"David\",\"David3@m.co\",\"David4@m.co\"],[\"David\",\"David4@m.co\",\"David5@m.co\"],[\"David\",\"David2@m.co\",\"David3@m.co\"],[\"David\",\"David1@m.co\",\"David2@m.co\"]]\n",
    "expected = [[\"David0@m.co\",\"David1@m.co\",\"David2@m.co\",\"David3@m.co\",\"David4@m.co\",\"David5@m.co\"]]\n",
    "pprint(inputs)\n",
    "\n",
    "print()\n",
    "\n",
    "outputs = makeGroups2(inputs)\n",
    "print()\n",
    "pprint(outputs)\n",
    "print()\n",
    "pprint(expected)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/accounts-merge\n",
    "\n",
    "\n",
    "\n",
    "Time Limit Exceeded\n",
    "\n",
    "\n",
    "\n",
    "```python\n",
    "from typing import List\n",
    "from collections import Counter\n",
    "\n",
    "def valid(inputs):\n",
    "    c = Counter()\n",
    "    for l in inputs:\n",
    "        c.update(l)\n",
    "    #print(c)\n",
    "    return all([v == 1 for v in c.values()])\n",
    "\n",
    "def makeGroups(inputs):\n",
    "    inputs = [set(input) for input in inputs]\n",
    "    outputs = [inputs[0]]\n",
    "    E0 = inputs[1:]\n",
    "    E1 = []\n",
    "    while True:\n",
    "        if len(E0) == 1:\n",
    "            e = E0[0]\n",
    "            fine = False\n",
    "            for index, target in enumerate(outputs):\n",
    "                if len(target & e) > 0:\n",
    "                    outputs[index] = outputs[index] | e\n",
    "                    fine = True\n",
    "            if fine == False:\n",
    "                if e not in outputs:\n",
    "                    outputs.append(e)\n",
    "            break\n",
    "\n",
    "        #print(E0)\n",
    "        #print(outputs)\n",
    "        for index, target in enumerate(outputs):\n",
    "            for e in E0:\n",
    "                if len(target & e) > 0:\n",
    "                    outputs[index] = outputs[index] | e\n",
    "                else:\n",
    "                    if e not in E1:\n",
    "                        E1.append(e)\n",
    "            E0 = E1\n",
    "            if len(E0) == 0:\n",
    "                break\n",
    "        if len(E0) == 0:\n",
    "            break\n",
    "        else:\n",
    "            if E0[0] not in outputs:\n",
    "                outputs.append(E0[0])\n",
    "                E0 = E0[1:]\n",
    "                E1 = E1[1:]\n",
    "    return outputs\n",
    "\n",
    "\n",
    "\n",
    "def makeGroups2(inputs):\n",
    "    while True:\n",
    "        outputs = makeGroups(inputs)\n",
    "        if valid(outputs):\n",
    "            return outputs\n",
    "        else:\n",
    "            inputs = outputs\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        raw_data = dict()\n",
    "        for account in accounts:\n",
    "            name = account[0]\n",
    "            if name in raw_data.keys():\n",
    "                raw_data[name].append(account[1:])\n",
    "            else:\n",
    "                raw_data[name] = [account[1:]]\n",
    "        results = []\n",
    "        for name, emails in raw_data.items():\n",
    "            groups = makeGroups2(emails)\n",
    "            for group in groups:\n",
    "                group = list(group)\n",
    "                group.sort()\n",
    "                results.append([name] + group)\n",
    "        return results\n",
    "```\n",
    "\n",
    "\n",
    "Spent two days.\n",
    "\n",
    "4 shoot."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}